package solution;

import java.util.Arrays;

/**
 * @author zhangmin
 * @create 2021-12-15 16:57
 * 只出现一次的数字
 */
public class Solution_14OnceInteger {

    /**==============================================================================================================================================
     * 136. 只出现一次的数字
     * 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
     * 直接位运算：一个数和它本身做异或运算结果为 0，一个数和 0 做异或运算的结果为它本身
     *  */
    public int singleNumber1(int[] nums) {
        int res=0;
        for (int n:nums) {
            res^=n;
        }
        return res;
    }

    /**==============================================================================================================================================
     * 剑指 Offer II 070. 排序数组中只出现一次的数字（540. 有序数组中的单一元素）
     * 给你一个仅由整数组成的有序数组，其中每个元素都会出现两次，唯有一个数只会出现一次。请你找出并返回只出现一次的那个数。
     * 1、暴力：从第一个元素开始，我们检查每个第二个元素是否与当前元素相同。 如果不同，说明该元素是单个元素。如果我们到达最后一个元素，则它为单一元素。
     * 2、二分：变量 halvesAreEven = (hi - mid) % 2 == 0确定中间元素的那一侧的元素个数是奇数，
     *              1：中间元素的同一元素在右边，且被 mid 分成两半的数组为偶数。则右子数组元素个数变成奇数，我们应将 lo 设置为 mid + 2。
     *              2：中间元素的同一元素在右边，且被 mid 分成两半的数组为奇数。则右子数组的元素个数变为偶数，我们应将 hi 设置为 mid - 1。
     *              3：中间元素的同一元素在左边，且被 mid 分成两半的数组为偶数。则左子数组的元素个数变为奇数，我们应将 hi 设置为 mid - 2。
     *              4：中间元素的同一元素在左边，且被 mid 分成两半的数组为奇数。则左子数组的元素个数变为偶数，我们应将 lo 设置为 mid + 1。
     * 3、只对偶数索引进行二分搜索：我们对所有偶数索引进行搜索，直到遇到第一个其后元素不相同的索引。
     *  */
    public int singleNonDuplicate1(int[] nums) {
        for (int i = 0; i < nums.length-1; i+=2) {
            if (nums[i]!=nums[i+1])
                return nums[i];
        }
        return nums[nums.length-1];
    }
    public int singleNonDuplicate2(int[] nums) {
        int left=0,right=nums.length-1;
        while (left<right){
            int mid=left+(right-left)/2;
            boolean halvesAreEven=(right-mid)%2==0;
            if (nums[mid+1]==nums[mid]){
                if (halvesAreEven){
                    left=mid+2;
                }else {
                    right=mid-1;
                }
            }else if (nums[mid-1]==nums[mid]){
                if (halvesAreEven){
                    right=mid-2;
                }else {
                    left=mid+1;
                }
            }else {
                return nums[mid];
            }
        }
        return nums[left];
    }
    public int singleNonDuplicate(int[] nums) {
        int lo = 0;
        int hi = nums.length - 1;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (mid % 2 == 1) mid--;
            if (nums[mid] == nums[mid + 1]) {
                lo = mid + 2;
            } else {
                hi = mid;
            }
        }
        return nums[lo];
    }
    /**==============================================================================================================================================
     * 剑指 Offer II 004. 只出现一次的数字 （137. 只出现一次的数字 II,剑指 Offer 56 - II. 数组中数字出现的次数 II）
     * 给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。
     * 1、依次确定每一个二进制位：考虑答案的第 i 个二进制位（i 从 0 开始编号），它可能为 0 或 1。对于数组中非答案的元素，
     * 每一个元素都出现了 3 次，对应着第 i 个二进制位的 3 个 0 或 3 个 1，无论是哪一种情况，它们的和都是 3 的倍数（即和为 0 或 3）。
     * 因此，答案的第 i 个二进制位就是数组中所有元素的第 i 个二进制位之和除以 3 的余数。
     *  */
    public int singleNumber2(int[] nums) {
        int res=0;
        for (int i = 0; i < 32; i++) {
            int total=0;
            for (int num:nums) {
                total+=((num>>i)&1);
            }
            if (total%3!=0){
                res|=(1<<i);
            }
        }
        return res;
    }
    public int singleNumber3(int[] nums) {
        int ones=0,twos=0;
        for (int n:nums) {
            ones=ones^n&~twos;
            twos=twos^n&~ones;
        }
        return ones;
    }

    /**==============================================================================================================================================
     * 260. 只出现一次的数字 III(NC75 数组中只出现一次的两个数字,剑指 Offer 56 - I. 数组中数字出现的次数)
     * 给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。
     * 位运算：假设数组 nums 中只出现一次的元素分别是 x_1和 x_2 。如果把 nums 中的所有元素全部异或起来，得到结果 x，那么一定有：x=x_1^x_2
     * 我们就可以把 nums 中的所有元素分成两类，其中一类包含所有二进制表示的第 l 位为 0 的数，另一类包含所有二进制表示的第 l 位为 1 的数。可以发现：
     * 对于任意一个在数组 nums 中出现两次的元素，该元素的两次出现会被包含在同一类中；
     * 对于任意一个在数组 nums 中只出现了一次的元素，即 x_1和 x_2，它们会被包含在不同类中。
     *  */
    public int[] singleNumbers(int[] nums) {
        //先将所有元素异或
        int res=0;
        for (int n:nums) {
            res^=n;
        }
        //在异或的结果中找到不为0的最低位
        int index=1;
        while ((index&res)==0) index<<=1;
        //依据第index位是否为1分组，然后每组内异或，得到两个数,index的中只有一位为1
        int a=0,b=0;
        for (int n:nums) {
            if ((index&n)!=0){
                a^=n;
            }else {
                b^=n;
            }
        }
        return new int[]{a,b};
    }
    public int[] FindNumsAppearOnce (int[] array) {
        int xorsum=0;
        for (int num: array) {
            xorsum^=num;
        }
        //防止溢出
        int flag=(xorsum==Integer.MIN_VALUE?xorsum:xorsum&(-xorsum));
        int x1=0,x2=0;
        for (int num:array) {
            if ((num&flag)!=0){
                x1^=num;
            }else {
                x2^=num;
            }
        }
        return x1<x2?new int[]{x1,x2}:new int[]{x2,x1};
    }

    /**==============================================================================================================================================
     * 剑指 Offer 39. 数组中出现次数超过一半的数字
     * 排序
     *  */
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length/2];
    }

    /**==============================================================================================================================================
     * NC156 数组中只出现一次的数（其它数出现k次）
     * 给定一个长度为 n 的整型数组 arr 和一个整数 k(k>1) 。已知 arr 中只有 1 个数出现一次，其他的数都出现 k 次。请返回只出现了 1 次的数。
     * 排序：排序后只需遍历k的倍数的下标位置
     *  */
    public int foundOnceNumber (int[] arr, int k) {
        Arrays.sort(arr);
        for (int i = 0; i < arr.length; i++) {
            if (arr[i]==arr[i+1]){
                i+=k-1;
            }else {
                return arr[i];
            }
        }
        return arr[arr.length-1];
    }
}
